package likou;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/07/12 11:38
 */
public class _84 {
    int res = 0;

    public int largestRectangleArea(int[] heights) {
        //用于记录某个下标，参与过哪些场合的计算，比如下标1，参与了高度2的，然后就需要直接退出，因为重复了。
        Set<Integer>[] set = new HashSet[heights.length];
        for (int i = 0; i < heights.length; i++) {
            bfs(set, i, heights);
        }
        return res;
    }

    public void bfs(Set<Integer>[] set, int i, int[] heights) {
        //当前节点，没有经历它自己的高度
        if (set[i]!=null){
            if (set[i].contains(heights[i])) {
                return;
            }
        }else {
            set[i] = new HashSet<>();
            set[i].add(heights[i]);
        }
        int now = heights[i];
        int sum = now;
        int left = i - 1, right = i + 1;
        while (left >= 0 && heights[left] >= now) {
            sum += now;
            if (set[left]==null){
                set[left] = new HashSet<>();
            }
            set[left].add(now);
            left--;
        }
        while (right < heights.length && heights[right] >= now) {
            sum += now;
            if (set[right]==null){
                set[right] = new HashSet<>();
            }
            set[right].add(now);
            right++;
        }
        res = Math.max(res, sum);
    }
}
